/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/longest-common-subsequence
@Language: C++
@Datetime: 16-02-09 05:56
*/

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string A, string B) {
        // write your code here
        static const int MAXLEN = 1000;
        int la = A.length();
    	int lb = B.length();
    	int i,j,len=0;
    	int DP[MAXLEN][MAXLEN];
    	for(i=0;i<la;++i)
    		DP[i][0]=0;
    	for(j=0;j<lb;++j)
    		DP[0][j]=0;
    	
    	for(i=1;i<=la;++i){
    		for(j=1;j<=lb;++j){
    			if (A[i-1]==B[j-1])
    				DP[i][j] = DP[i-1][j-1]+1;
    			else
    				DP[i][j] = (DP[i][j-1]>DP[i-1][j]?DP[i][j-1]:DP[i-1][j]);
    		}
    	}
    	return DP[la][lb];
    }
};
